\section{Implémentation de la méthode de re-distribution}

Cette section contiendra tous les détails et toutes les explications concernant l'implémentation de la solution, réalisée en Java pour ce mémoire. Dans un premier temps, nous verrons l'ensemble des classes qui constitue le programme et les méthodes intéressantes de ces classes. 

\subsection{Les classes}

Il y a trois \textit{packages} dans l'application Java qui permettent de différencier les trois types de classes. Tout d'abord, il y a les classes qui définissent le graphe et sa structure; ensuite, il y a les classes qui sont nécessaires à la comparaison et à la redistribution; enfin, il y a les classes de \textit{parsing}.

\subsubsection{La classe \textsl{Color} (structure du graphe)}

\noindent
Une couleur est définie par deux attributs: 
\medskip

\begin{itemize}
	\item \textsl{name}: chaîne de caractère qui contient le nom de la couleur;
	\item \textsl{constraintNb}: entier qui contient l'\textsl{ID} de contrainte assignée à cette couleur.
\end{itemize}

\medskip
Cette classe est nécessaire pour assigner une couleur à une contrainte. Pour la couleur spéciale, le blanc, l'\textsl{ID} de la contrainte est fixé à -1, ce qui signifie, en réalité, qu'il n'existe pas de contrainte.

\subsubsection{La classe \textsl{Variables} (structure de graphe)}

\noindent
Une variable est définie par deux attributs: 
\medskip

\begin{itemize}
	\item \textsl{name}: chaîne de caractère qui contient le nom de la variable;
	\item \textsl{constraint}: entier qui contient l'\textsl{ID} de la contrainte imposée à la variable (ou -1, si aucune contrainte n'est imposée).
\end{itemize}

\medskip
Cette classe sert à stocker les variables et est utilisée dans la définition d'une instruction (voire plus bas).

\subsubsection{La classe \textsl{Instructions} (structure de graphe)}

\noindent
Une instruction est définie par un ensemble d'attributs : 
\medskip

\begin{itemize}
	\item \textsl{atomic}: booléen qui indique si l'instruction est atomique ou non;
	\item \textsl{label}: chaîne de caractère qui contient le label de l'instruction;
	\item \textsl{variables}: liste contenant toutes les variables utilisées par cette instruction;
	\item \textsl{position}: chaîne de caractère qui contient la position de l'instruction. La position est, par exemple, le titre de la \texttt{SEQUENCE}, de la \texttt{METHOD}, la condition du \texttt{IF}, etc.;
	\item \textsl{next}: liste de toutes les instructions qui peuvent suivre (dans le code). Majoritairement, cette liste ne contiendra qu'un seul élément, sauf dans le cas des \texttt{IF} ou des \texttt{WHILE}. En effet, pour le \texttt{IF}, il y a trois instructions qui peuvent suivre: (i) la première instruction du \texttt{IF} (condition vraie), (ii) la première instruction du \texttt{ELSE} (condition fausse), et (iii) la première instruction qui suit le bloc \texttt{IF} (condition impossible à évaluer).
\end{itemize}

\medskip
Cette classe sera nécessaire pour la définition d'un n\oe{}ud (voire plus bas).

\subsubsection{La classe \textsl{Node} (structure de graphe)}

\noindent
Un n\oe{}ud est défini par deux attributs: 
\medskip

\begin{itemize}
	\item \textsl{color}: une couleur;
	\item \textsl{instruction}: l'instruction que représente le n\oe{}ud.
\end{itemize}

\medskip
Cette classe constitue une partie de la structure du graphe (classe \textsl{Graph}, voire plus bas), l'autre partie étant les arcs (classe \textsl{Edges}, voir ci-dessous).

\subsubsection{La classe \textsl{Edges} (structure de graphe)}

\noindent
Un arc est défini par trois attributs: 
\medskip

\begin{itemize}
	\item \textsl{node1}: un n\oe{}ud qui définit une extrémité de l'arc;
	\item \textsl{node2}: un n\oe{}ud qui définit l'autre extrémité de l'arc;
	\item \textsl{weight}: un nombre à point flottant qui définit le poids de l'arc.
\end{itemize}

\medskip
Cette classe permet de créer des arcs entre les n\oe{}uds du graphe. Il faut quand même préciser que cette classe est utilisée tant pour la définition des graphes de comparaison que pour la définition du graphe de coloration. Dans le cas des graphes de comparaison, le dernier attribut n'est pas nécessaire et donc n'est pas utilisé. En revanche, cet attribut est évidemment utilisé dans la coloration, puisqu'il joue un rôle primordial dans le calcul du coût de transmission. Même si les noms des variables (\textsl{node1} et \textsl{node2}) peuvent le laisser penser, les arcs sont non dirigés.

\subsubsection{La classe \textsl{Graph} (structure de graphe)}

\noindent
Un graphe est défini par trois attributs: 
\medskip

\begin{itemize}
	\item \textsl{nodes}: la liste de tous les n\oe{}uds qui constituent le graphe;
	\item \textsl{edges}: la liste de tous les arcs qui constituent le graphe;
	\item \textsl{colors}: la liste de toutes les couleurs utilisées dans le graphe.
\end{itemize}

\medskip
Cette classe définit donc la structure du graphe avec l'ensemble des n\oe{}uds et des arcs qu'elle contient. Étant donné que les graphes utilisés pour la comparaison sont associés à une version du programme \textsl{dSL}, le troisième attribut sert à conserver l'ensemble des couleurs qui peuvent être utilisées dans cette version du code ainsi que l'\textsl{ID} de la contrainte à laquelle ces couleurs sont associées.

\subsubsection{La classe \textsl{NodesCouple} (comparaison-redistribution)}

\noindent
Un couple de n\oe{}uds est défini par deux attributs: 
\medskip

\begin{itemize}
	\item \textsl{node1}: le premier n\oe{}ud du couple;
	\item \textsl{node2}: le second n\oe{}ud du couple.
\end{itemize}


\medskip
Cette classe est utilisée lors de la comparaison. En effet, le but de la comparaison est de créer un \textit{matching} entre les n\oe{}uds du premier et les n\oe{}uds du second graphe. Ce \textit{matching} est représenté par un ensemble de couple de n\oe{}uds dans lequel \textsl{node1} appartient au premier graphe et \textsl{node2} appartient au second graphe.

\subsubsection{La classe \textsl{Redistribution} (comparaison-redistribution)}

\noindent
Cette classe réalise effectivement tout le processus de redistribution (comparaison et coloration). Elle est définie par une série d'attributs: 
\medskip

\begin{itemize}
	\item \textsl{newGraph}: un graphe qui contient une copie du second graphe. C'est lui qui, à la fin du processus de redistribution, sera coloré;
	\item \textsl{compareGraph1}: le graphe de comparaison, construit à partir du graphe associé à la première version du code de l'application;
	\item \textsl{compareGraph2}: le graphe de comparaison, construit à partir du graphe associé à la seconde version du code de l'application;
	\item \textsl{MCS}: un graphe qui contient le \textsl{MCS} (\textit{Maximum Common Subgraph}), après le processus de comparaison des deux graphes (\textsl{compareGraph1} et \textsl{compareGraph2});
	\item \textsl{recolorationGraph}: le graphe de coloration, construit à partir du graphe associé à la seconde version du code de l'application;
	\item \textsl{colors}: une copie des couleurs utilisées dans le second graphe (ceci est utile pour éviter des passages de paramètres);
	\item \textsl{bestAssignation}: une liste des n\oe{}uds séquentiels qui sont colorés de telle manière à obtenir le meilleur compromis entre les deux coûts;
	\item \textsl{minCostValue}: un flottant qui représente le plus petit coût d'optimalité;
	\item \textsl{alpha}: un flottant qui représente le paramètre $\alpha$ dans la formule du coût d'optimalité;
	\item \textsl{beta}: un flottant qui représente le paramètre $\beta$ dans la formule du coût d'optimalité;
	\item \textsl{psi}: un flottant qui représente le paramètre $\psi$, c'est-à-dire le pourcentage de chance qu'une condition d'un \texttt{IF ... THEN ... ELSE ... END\_IF} ne soit pas correctement évaluée;
	\item \textsl{p}: un flottant qui représente le pourcentage de chance qu'une condition d'un \texttt{IF} soit évaluée à vrai;
	\item \textsl{k}: un entier qui représente le nombre de fois qu'une boucle \texttt{WHILE} est effectuée (en moyenne).
\end{itemize}

\medskip
Cette classe sert à effectuer tout le processus de redistribution. Tout d'abord, la comparaison sera effectuée (en créant, à partir du premier et du second graphe, les deux graphes de comparaison). Après la comparaison et la pré-coloration, c'est la finition de la coloration qui est effectuée (avec le calcul du coût d'optimalité sur base du graphe de coloration créé au préalable).

\subsubsection{La classe \textsl{ColorsParser} (\textit{parsing})}

Cette classe sert à lire les fichiers contenant les différentes couleurs utilisées dans la première et la seconde version du programme \textsl{dSL}. Après cette étape de \textit{parsing}, la liste des couleurs sera ajoutée au graphe correspondant à la version du programme.

\subsubsection{La classe \textsl{VariablesParser} (\textit{parsing})}

Cette classe sert à lire les fichiers contenant l'ensemble des variables utilisées dans les deux versions du programme \textsl{dSL}. Après cette étape de \textit{parsing}, la liste des variables sera utilisée dans la définition des instructions qui seront \textit{parsées} pendant le processus de \textit{parsing} des n\oe{}uds. 

\subsubsection{La classe \textsl{NodesParser} (\textit{parsing})}

Cette classe sert à lire les fichiers contenant l'ensemble des n\oe{}uds représentant les instructions des deux versions du programme \textsl{dSL}. Après cette étape de \textit{parsing}, la liste des n\oe{}uds sera donnée au graphe correspondant à la version du programme. Il ne restera, alors, plus qu'à générer les arcs entre les n\oe{}uds pour obtenir un graphe complet.

\subsection{Les méthodes intéressantes}

Nous présentons, ci-dessous, une liste des méthodes que nous jugeons importantes pour la compréhension du fonctionnement du programme. Les autres méthodes ne sont que des méthodes de type \textsl{get/set} ou des constructeurs que nous ne jugeons pas nécessaire de présenter ici.

\subsubsection{La méthode \textsl{mustBeLinkedTo} (classe \textsl{Node})}

Cette méthode, qui prend un autre n\oe{}ud en paramètre, permet de définir si les deux n\oe{}uds (celui sur lequel la méthode est appelée et celui passé en paramètre) doivent être reliés par un arc dans le graphe. Les conditions pour que deux n\oe{}uds soient reliés sont les suivantes : 
\medskip

\begin{itemize}
	\item Les deux n\oe{}uds représentent des instructions qui utilisent la même variable;
	\item Les deux n\oe{}uds représentent des instructions qui sont consécutives dans un \texttt{WHEN};
\end{itemize}

\medskip
Lorsqu'une de ces trois conditions est satisfaite, la méthode renvoie \textit{vrai} signifiant que les deux n\oe{}uds doivent être reliés par un arc. 

\subsubsection{La méthode \textsl{colorGraph} (classe \textsl{Graph})}

Cette méthode, qui prend le \textsl{MCS} en paramètre, permet d'effectuer la pré-coloration du second graphe. Elle fonctionne de la manière suivante, pour chaque n\oe{}ud du second graphe : 
\medskip

\begin{enumerate}
	\item ce n\oe{}ud possède une contrainte: on appelle la méthode \textsl{colorNode} (voir plus bas) en donnant, en paramètre, le n\oe{}ud et la couleur correspondante à la contrainte;
	\item ce n\oe{}ud ne possède pas de contrainte: on regarde, dans le \textsl{MCS} (s'il s'y retrouve), le n\oe{}ud du premier graphe auquel il est \textit{matché} et on lui assigne la couleur de ce dernier.
\end{enumerate}	

\subsubsection{La méthode \textsl{colorNode} (classe \textsl{Graph})}

Cette méthode, qui prend un n\oe{}ud et une couleur en paramètre, permet de colorer le n\oe{}ud passé en paramètre ainsi que tous les autres n\oe{}uds de la même composante connexe. Elle va donc parcourir tous les arcs du graphe et, si le n\oe{}ud passé en paramètre est une extrémité d'un arc, la méthode sera appelée récursivement sur l'autre extrémité de cet arc.

\subsubsection{La méthode \textsl{removeNodeFromGraph} (classe \textsl{Graph})}

Cette méthode, qui prend un n\oe{}ud en paramètre, permet de retirer ce n\oe{}ud du graphe. Lorsqu'un n\oe{}ud est retiré, il faut retirer les arcs qui ont ce n\oe{}ud pour extrémité. De plus, comme cette méthode est utilisée pour la construction du graphe de comparaison, si on retire un n\oe{}ud, c'est qu'une contrainte lui est imposée. Dès lors, tout le composant connexe dans lequel il se trouve peut être retiré du graphe puisque la contrainte porte également sur tous les autres n\oe{}uds qui le compose. La méthode est donc appelée récursivement sur l'autre extrémité des arcs supprimés.

\subsubsection{La méthode \textsl{generateEdges} (classe \textsl{Graph})}

Cette méthode va faire une double boucle sur les noeuds du graphe afin de déterminer, grâce à la méthode \textsl{mustBeLinkedTo}, si un arc doit être créé entre chaque couple de n\oe{}uds possible (sans créer de doublons).

\subsubsection{La méthode \textsl{constructCompGraph} (classe \textsl{Redistribution})}

Cette méthode va permettre de construire le graphe de comparaison à partir du graphe passé en paramètre. Pour chaque n\oe{}ud de ce graphe, il va falloir regarder s'il existe une contrainte imposée à ce n\oe{}ud. Si c'est le cas, ce n\oe{}ud et tous les autres n\oe{}uds qui se trouvent dans le même composant connexe sont retirés.

\subsubsection{La méthode \textsl{constructRecolorationGraph} (classe \textsl{Redistribution})}

Cette méthode va, à partir du graphe représentant la seconde version du programme, construire le graphe utilisé pour la finition de la coloration. Pour ce faire, la méthode parcourt tous les n\oe{}uds de ce graphe et ne retient que ceux qui ne sont pas atomiques. Dès qu'un tel n\oe{}ud $n$ a été trouvé, la méthode va récupérer tous les n\oe{}uds représentant les instructions qui suivent l'instruction représentée par $n$. Pour chacun de ces n\oe{}uds, il va falloir créer un arc (sans créer de doublons) et en calculer le poids. Il y a deux étapes pour calculer le poids d'un arc. La première consiste à calculer le poids de base de l'arc. Pour ceci, plusieurs règles (nommons $n_1$ et $n_2$, les deux n\oe{}uds qui constistuent l'arc traité) existent: 
\medskip

\begin{enumerate}
	\item $n_1$ représente une condition d'un \texttt{IF ... THEN ... ELSE ... END\_IF} et $n_2$ représente la première instruction de la branche \textit{vraie} de ce \texttt{IF}: le poids est de $p - (\frac{\psi}{2})$;
	\item $n_1$ représente une condition d'un \texttt{IF ... THEN ... END\_IF} et $n_2$ représente la première instruction de la branche \textit{vraie} de ce \texttt{IF}: le poids est de $p$;
	\item $n_1$ représente la condition d'un \texttt{IF ... THEN ... ELSE ... END\_IF} et $n_2$ représente la première instruction de la branche \textit{fausse} de ce \texttt{IF}: le poids est de $1 - p - (\frac{\psi}{2})$;
	\item $n_1$ représente la condition d'un \texttt{IF ... THEN ... END\_IF} et $n_2$ représente la première instruction qui suit ce bloc \texttt{IF}: le poids est de $1 - p$;
	\item $n_1$ représente la condition d'un \texttt{IF ... THEN ... ELSE ... END\_IF} et $n_2$ représente la première instruction qui suit ce bloc \texttt{IF}: le poids est de $\psi$;
	\item $n_1$ représente la condition d'un \texttt{WHILE} et $n_2$ représente la première instruction à l'intérieur de ce bloc \texttt{WHILE}: le poids est de $k$;
	\item $n_1$ représente la condition d'un \texttt{WHILE} et $n_2$ représente la première instruction qui suit ce bloc \texttt{WHILE}: le poids est de $1$;
	\item $n_1$ et $n_2$ représentent deux instructions qui se suivent dans un même bloc: le poids est de $1$.
\end{enumerate}

\medskip
La seconde étape consiste à faire passer les poids par héritage (pour les imbrications des blocs). Pour ce faire, on parcourt les arcs déjà établis et, si le n\oe{}ud traité est l'extrémité d'un de ces arcs, on multiplie le poids en cours de calcul par le poids de l'arc trouvé. Pour mieux comprendre ce principe d'héritage, prenons un exemple simple: soient trois n\oe{}uds $n_1$, $n_2$ et $n_3$. $n_1$ représente la condition d'un \texttt{IF ... THEN ... END\_IF}, $n_2$ représente la première instruction dans la branche \textit{vraie} du \texttt{IF} et $n_3$ représente l'instruction qui suit celle représentée par $n_2$. Selon la deuxième règle ci-dessus, l'arc entre $n_1$ et $n_2$ possède un poids de $p$. Selon la dernière règle ci-dessus, l'arc entre $n_2$ et $n_3$ vaut $1$. Or, avec l'héritage, on va multiplier le poids de l'arc $(n_2, n_3)$ par le poids de l'arc $(n_1, n_2)$. Au final, l'arc $(n_2, n_3)$ aura un poids égal à $p$, ce qui est le poids désiré au sein d'un \texttt{IF}.

\subsubsection{La méthode \textsl{compare} (classe \textsl{Redistribution})}

Cette méthode va créer l'ensemble \textit{matching} qui contient toutes les paires de n\oe{}uds qui se ressemblent (entre la première et la seconde version du graphe). Pour ce faire, la méthode va faire une boucle dans laquelle elle construit un ensemble de paires candidates. La boucle s'arrête lorsqu'on arrive plus à construire un ensemble de paires candidates ou lorsque celui-ci est le même qu'au tour de boucle précédent. Quand un tel ensemble est construit, on tente de chercher une paire de n\oe{}uds telle que les attributs de ces n\oe{}uds sont les mêmes. Lorsqu'une telle paire est trouvée, elle est ajoutée à l'ensemble $M$ (l'ensemble de \textit{matching}). Ensuite, l'ensemble des paires candidates est vidé et reconstruit (la manière de construire un tel ensemble de paires candidates et la même que celle utilisée pour la construction de $P(s)$ dans l'algorithme \textsl{VF2}, décrite en section~\ref{vf2Algo}).

\subsubsection{La méthode \textsl{coloration} (classe \textsl{Redistribution})}

Cette méthode va, tout d'abord, effectuer la pré-coloration via l'appel de la méthode \textsl{colorGraph} sur le graphe qui représente la seconde version du programme. Après cette étape de pré-coloration, la méthode va faire une copie des n\oe{}uds du graphe de coloration (pour conserver la pré-coloration, dans le but de calculer le coût d'optimalité). Après cette copie, la méthode va, enfin, appeler la méthode \textsl{recolor} qui va se charger d'effectuer la coloration en conservant un coût minimal. À la fin de cette méthode, le graphe de la seconde version du programme sera entièrement coloré.

\subsubsection{La méthode \textsl{recolor} (classe \textsl{Redistribution})}

Cette méthode va tenter de finir la coloration en minimisant le coût d'optimalité. Il s'agit d'une méthode récursive qui construit petit à petit une solution. La méthode prend en paramètre un indice qui définit le n\oe{}ud dans le vecteur qui doit être coloré. Lorsque l'indice sort du vecteur, le coût est calculé. Si la solution construite est faisable et que le coût calculé est plus petit que ce qu'on a déjà calculé auparavant, la solution est retenue et la valeur minimale du coût est mise à jour. La récursion est très simple: on boucle sur chaque couleur possible, on colore le n\oe{}ud qui possède l'indice reçu en paramètre, on augmente cet indice et on rappelle la méthode. Pour éviter d'énumérer toutes les solutions, lorsqu'on est en train de construire une solution, si son coût dépasse le minimum déjà calculé, la recherche est arrêtée.

\subsubsection{La méthode \textsl{computeCost} (classe \textsl{Redistribution})}

Cette méthode, qui prend la pré-coloration en paramètre, calcule le coût d'optimalité de la coloration finale. Pour chaque n\oe{}ud, si celui-ci a changé de couleur par rapport à la pré-coloration (et qu'il n'était pas blanc), le coût est augmenté de $1 * \alpha$. Ensuite, pour chaque n\oe{}ud, on regarde tous les liens du graphe de coloration qui parte de ce n\oe{}ud et, si l'autre extrémité de cet arc ne possède pas la même couleur, le coût est augmenté de $poids\_arc * \beta$.

\subsubsection{La méthode \textsl{isFeasible} (classe \textsl{Redistribution})}

Cette méthode va vérifier que l'assignation de couleur est faisable, c'est-à-dire qu'elle respecte bien toutes les contraintes. Pour chaque n\oe{}ud $n$, elle va vérifier que, si un contrainte était imposée à $n$, sa couleur est bien la même que celle de la contrainte. De plus, pour chaque arc du graphe qui représente la seconde version du programme, si $n$ est une des extrémité d'un arc, l'autre extrémité doit être de la même couleur.

\subsection{Remarques}

Quelques remarques doivent être évoquées pour être le plus complet possible dans l'explication de cette implémentation. \\

\begin{description}
	\item[Le \textsl{parsing} est simplifié: ] il est censé pouvoir lire le fichier intermédiaire \textsl{XML} mis en place lors du stage (voir section~\ref{rapport-stage}), or il ne lit qu'un fichier \textsl{XML} très simplifié, ne contenant que des informations nécessaires (comme les différentes couleurs, les différentes variables et les différents n\oe{}uds). Ceci dit, il n'est pas très compliqué de ré-écrire les classes de \textit{parsing} afin qu'elles lisent les fichiers intermédiaires prévus.
	
	\item[L'imbrication des structures] n'est pas gérée à 100\% dans cette implémentation (par manque de temps). En effet, dans la méthode \textsl{mustBeLinkedTo}, si un bloc \texttt{IF} ou un bloc \texttt{WHILE} se trouve dans un \texttt{WHEN}, les instructions de ces blocs imbriqués ne seront pas liés entre eux. Il suffirait de chercher si on se trouve pas dans un \texttt{WHEN} lorsqu'on vérifie si deux n\oe{}uds doivent être liés.
	
	\item[Le paramètre \textsl{k}] est le même pour tous les \texttt{WHILE}. Il serait possible d'imaginer de permettre au programmeur de fixer un \textsl{k} pour chaque \texttt{WHILE}. Il suffirait, alors, de ré-écrire les fonctions de \textit{parsing} ainsi que de modifier un peu la structure de certaines classes pour mettre cette idée en place.
\end{description}